public class code3 {

    // 牛客 top 101 寻找 topK
    // 这里使用的是优先级队列解决 topK 问题

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        // write code here
        // 这里可以使用一个优先级队列来进行排序
        // 先来创建一个优先级队列
        PriorityQueue<Integer> que = new PriorityQueue<>(new MyComparator());
        int[] b = new int[n];
        int flag1 = 0;
        int flag2 = 0;
        int k = 0;

        for (int i = 0; i < a.length; i++) {
            que.offer(a[i]);
        }

        while(!que.isEmpty()) {
            b[flag1] = que.poll();
            System.out.println(b[flag1]);
            flag1++;
        }

        // 在 b 数组中尝试找到第 k 大的值
        while(k != K) {
            int topK = b[flag2];
            flag2++;
            if(topK >= b[flag2]){
                k++;
            }
        }

        // 需要注意的是，在上面找到第 k 大的值时，会对 k 的值多一次
        // 准确的来讲，这里的 k 值的位置是要在 k-1 处的！！！
        return b[k-1];
    }

    //PriorityQueue默认从小到大输出，这里自定义比较器让其从大到小输出
    class MyComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer i1, Integer i2) {
            return i2 - i1;
        }

    }
}
